1. Field of the Invention
The present invention relates to a controller and a memory system.
2. Description of the Related Art
Memory systems (e.g., Solid State Disks [SSDs]) each of which includes a large number of flash memories and a memory controller that manages data stored in the flash memories have conventionally been known.
In such a memory system, the memory controller refers to a translation table in which logical addresses and physical addresses in the flash memories are kept in correspondence with one another and searches for a physical address that corresponds to a logical address notified by a host apparatus such as a personal computer (PC). According to the contents of an instruction that has been received from the host apparatus together with the logical address, the memory controller writes data into, reads data from, or deletes data from, an area in the flash memories indicated by the physical address that has been found in the search.
The data stored in the flash memories is processed in units of: “pages” each of which is normally an area itself that is indicated by a physical address and is the smallest processing unit; and “blocks” each of which is a processing unit containing a plurality of pages.
Unlike Hard Disk Drives (HDDs) and the like, flash memories have characteristics as follows: it is not possible to write a new piece of data into an area in which another piece of data has already been written, unless the written piece of data is erased first; it is possible to erase the data only in units of blocks; and when the data erasing process is repeatedly performed, physical deterioration of the flash memories occurs.
For this reason, in the memory systems as described above, the memory controller manages information (hereinafter, “File Allocation Table [FAT] information”) indicating whether the data stored in the pages is valid, invalid, or deleted (see, for example, JP-A 2006-216036 (KOKAI)). The memory controller also realizes deletions and overwriting of the data by, for example, rewriting the FAT information, so that it is possible to avoid the situation in which, every time a delete instruction or an overwrite instruction is issued by the host apparatus, the data is actually erased from the flash memories in units of blocks.
For example, in a data overwriting process, the memory controller writes a new piece of data used for overwriting an old piece of data into a page that is different from the page in which the old piece of data is stored. The memory controller then updates a piece of FAT information of the page in which the old piece of data is stored so as to be invalid, and also updates the correspondence relationship between the logical addresses and the physical addresses.
Next, the correspondence relationships between blocks and pieces of FAT information before and after a data overwriting process is performed in a conventional memory system as described in, for example, JP-A 2006-216036 (KOKAI) will be explained, with reference to FIGS. 29 and 30.
FIG. 29 is a schematic drawing for explaining the state of the blocks and the pieces of FAT information before a data overwriting process is performed in a conventional memory system as described in, for example, JP-A 2006-216036 (KOKAI). In the example shown in FIG. 29, a state in which data is stored in each of all the pages in a block X is shown. Each of the pieces of FAT information of these pages indicates “V”, which means “valid”.
FIG. 30 is a schematic drawing for explaining the state of the blocks and the pieces of FAT information after a data overwriting process is performed in a conventional memory system as described in, for example, JP-A 2006-216036 (KOKAI). In the example shown in FIG. 30, a state is shown in which a new piece of data used for overwriting a piece of data stored in a page 901 in the block X has been written in a page 902 in a block Y. The piece of FAT information of the page 901 has been updated so as to indicate “IV”, which means “invalid”.
In the state shown in FIG. 30, the correspondence relationships between the logical addresses and the physical addresses are updated in the translation table. The logical address corresponding to a physical address X7 indicating the page 901 is brought into correspondence with a physical address Y1 indicating the page 901 (not shown).
However, in the conventional memory system as described above, no FAT information is managed for the pages in the block (e.g., the block Y in the example shown in FIG. 30; and a log block in the example shown in JP-A 2006-216036 (KOKAI)) that is to store therein the data to be written during a data overwriting process or the like.
As a result, for such blocks of which no FAT information is managed, it is not possible to manage the state of the data stored in the pages contained in each of those blocks. Thus, in some cases, storage areas in the flash memories are not effectively utilized.
For example, in the state shown in FIG. 30, even if a delete instruction for the page 902 has been issued, it is not possible for the memory system to remember that the data stored in the page 902 is deleted data, because there is no FAT information.
For this reason, the data can actually be deleted only in the case where an instruction instructing that the data stored in the pages of a block should all be deleted has been received from the host apparatus. In other words, when there is a block in which none of the pages store therein valid data, it is not possible to erase the data immediately so as to bring the block back into a state where a new piece of data can be written thereto. Thus, there is a possibility that the number of writable blocks may needlessly decrease and that fragmentation may occur in the flash memories.